home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackNode.h < prev    next >
Encoding:
Text File  |  1997-06-28  |  2.1 KB  |  73 lines  |  [TEXT/CWIE]
  1. // RedBlackNode.h
  2.  
  3. #ifndef RedBlackNode_h
  4. #define RedBlackNode_h
  5.  
  6. #ifndef TreeNode_h
  7. #include "TreeNode.h"
  8. #endif
  9.  
  10. class RedBlackNode: private TreeNode
  11.   {
  12.     friend class RedBlackTree;
  13.     
  14.     private:
  15.         bool red;
  16.  
  17.         bool IsRed() const                                { return red; }
  18.         bool IsBlack() const                                { return !red; }
  19.         uint32 RedChildren() const;
  20.         
  21.         void SwapWith( RedBlackNode& );
  22.         void RotateUp();
  23.  
  24.         void Raise();
  25.         void Lower();
  26.         
  27.         static RedBlackNode *DownCast( TreeNode *n )                    { return static_cast< RedBlackNode* >( n ); }
  28.         static const RedBlackNode *DownCast( const TreeNode *n )    { return static_cast< const RedBlackNode* >( n ); }
  29.  
  30.         static RedBlackTree& DownCast( Tree& n );
  31.         static const RedBlackTree& DownCast( const Tree& n );
  32.         
  33.     public:
  34.         RedBlackNode();
  35.         ~RedBlackNode();
  36.         
  37.         TreeNode::Owned;
  38.         RedBlackTree& Owner()                        { return DownCast( TreeNode::Owner() ); }
  39.         const RedBlackTree& Owner() const        { return DownCast( TreeNode::Owner() ); }
  40.  
  41.         RedBlackNode *Parent()                        { return DownCast( TreeNode::Parent() ); }
  42.         const RedBlackNode *Parent() const        { return DownCast( TreeNode::Parent() ); }
  43.  
  44.         RedBlackNode *Left()                            { return DownCast( TreeNode::Left() ); }
  45.         const RedBlackNode *Left() const            { return DownCast( TreeNode::Left() ); }
  46.  
  47.         RedBlackNode *Right()                        { return DownCast( TreeNode::Right() ); }
  48.         const RedBlackNode *Right() const        { return DownCast( TreeNode::Right() ); }
  49.         
  50.         RedBlackNode *Next()                            { return DownCast( TreeNode::Next() ); }
  51.         const RedBlackNode *Next() const            { return DownCast( TreeNode::Next() ); }
  52.  
  53.         RedBlackNode *Previous()                    { return DownCast( TreeNode::Previous() ); }
  54.         const RedBlackNode *Previous() const    { return DownCast( TreeNode::Previous() ); }
  55.  
  56.         RedBlackNode *Sibling()                        { return DownCast( TreeNode::Sibling() ); }
  57.         const RedBlackNode *Sibling() const        { return DownCast( TreeNode::Sibling() ); }
  58.         
  59.         TreeNode::IsRoot;
  60.         TreeNode::IsLeftChild;
  61.         TreeNode::IsRightChild;
  62.         
  63.         TreeNode::HasLeftChild;
  64.         TreeNode::HasRightChild;
  65.         TreeNode::IsLeaf;
  66.         
  67.         TreeNode::Depth;
  68.         
  69.         bool Valid( uint32 blackHeight ) const;        // Should always be true
  70.   };
  71.  
  72. #endif
  73.